//冒泡排序
//以i控制的每一轮外层循环过后，该轮最大的数字都会被放到最后面，并且下一轮就不再动这个位置，因此j的上限是length-i-1

//第一种方法时间复杂度为O(n2)，空间复杂度为O(1)
//第二种方法在逆序的情况下复杂度与第一种相同。如果数组已经有序，不需要进行交换只需要进行一轮比较，则为O(n)，空间复杂度为O(1)

public class bubbleSort {
    public static void main(String[] args) {

        int[] nums = new int[]{1, 4, 5, 7, 2, 6, 3};
//        bubbleSort(nums);
        betterBubbleSort(nums);
        for(int i = 0 ; i < 7 ; i++){
            System.out.println(nums[i]);
        }

    }

    public static int[] bubbleSort(int[] nums){
        for(int i = 0 ; i < nums.length ; i++){
            for(int j = 0 ; j < nums.length - 1 - i ; j++){
                if(nums[j] > nums[j+1]){
//                    这种交换的写法效果与一般的交换相同，但是加减的运算可能带来溢出的问题
//                    nums[j+1] = nums[j] + nums[j+1];
//                    nums[j] = nums[j+1] - nums[j];
//                    nums[j+1] = nums[j+1] - nums[j];

//                    因此可以采用异或解决，避免溢出，也是两个变量
                    nums[j+1] = nums[j] ^ nums[j+1];
                    nums[j] = nums[j+1] ^ nums[j];
                    nums[j+1] = nums[j+1] ^ nums[j];
                }
            }
        }
        return nums;
    }

//    冒泡排序的一种改良写法，用一个boolean标记是否交换过位置
    public static int[] betterBubbleSort(int[] nums){
        boolean swap = true;
        for(int i = 0 ; i < nums.length ; i++){
//            用swap来标记一轮中是否进行过交换位置，如果一轮都没有交换过一次，那么最终swap还是会保持为false，那么下一轮就不用再进行了，因为说明剩下的数字已经有序，可以结束
//            比第一种节省了时间，不用每个位置都进行比较
            if(!swap){
                break;
            }
            for(int j = 0 ; j < nums.length - 1 - i ; j++){
                if(nums[j] > nums[j+1]){
                    nums[j+1] = nums[j] ^ nums[j+1];
                    nums[j] = nums[j+1] ^ nums[j];
                    nums[j+1] = nums[j+1] ^ nums[j];

                    swap= true;
                }
            }
        }
        return nums;
    }
}
